package org.ala.linshen.dp;

/**
 * 给你一个数组 nums 和一个整数 k 。你需要找到 nums 的一个
 * 子数组
 *  ，满足子数组中所有元素按位或运算 OR 的值与 k 的 绝对差 尽可能 小 。换言之，你需要选择一个子数组 nums[l..r] 满足 |k - (nums[l] OR nums[l + 1] ... OR nums[r])| 最小。
 *
 * 请你返回 最小 的绝对差值。
 *
 * 子数组 是数组中连续的 非空 元素序列。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,4,5], k = 3
 *
 * 输出：0
 *
 * 解释：
 *
 * 子数组 nums[0..1] 的按位 OR 运算值为 3 ，得到最小差值 |3 - 3| = 0 。
 *
 * 示例 2：
 *
 * 输入：nums = [1,3,1,3], k = 2
 *
 * 输出：1
 *
 * 解释：
 *
 * 子数组 nums[1..1] 的按位 OR 运算值为 3 ，得到最小差值 |3 - 2| = 1 。
 *
 * 示例 3：
 *
 * 输入：nums = [1], k = 10
 *
 * 输出：9
 *
 * 解释：
 *
 * 只有一个子数组，按位 OR 运算值为 1 ，得到最小差值 |10 - 1| = 9 。
 *
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 105
 * 1 <= nums[i] <= 109
 * 1 <= k <= 109
 *
 * @author ala
 * @date 2024-10-09 08:55
 */
public class Q3171 {

    public static void main(String[] args) {
        Q3171 q = new Q3171();

//        int[] nums = {1,2,4,5};
//        int k = 3;

//        int[] nums = {1,3,1,3};
//        int k = 2;

//        int[] nums = {1};
//        int k = 10;

//        int[] nums = {6};
//        int k = 2;

        int[] nums = {20,10,7,4,65};
        int k = 14;

        System.out.println(q.minimumDifference(nums, k));
    }

    public int minimumDifference(int[] nums, int k) {
        return V1(nums, k);
    }
    /**
     *  1）滑窗，维护：窗口内所有元素的or值 和 没个位置1的数量
     *      滑窗右移时，or值在增大
     *      滑窗左移时，or值在减小
     *  2）每次移动滑窗时：
     *      维护窗口内每个位置1的数量
     *      计算or值
     *      计算 |k - or值|，并记录最小值
     */
    protected int V1(int[] nums, int k) {
        int N = nums.length;
        int or = 0, l = 0, r = -1;
        int[] bits = new int[32];

        int mn = Integer.MAX_VALUE;
        while (r < N - 1) {
            or = moveRight(nums[++r], bits, or);
            while (l < r && or > k) {
                mn = Math.min(mn, Math.abs(k - or));
                or = moveLeft(nums[l++], bits, or);
            }
            if (or == k) {return 0;}
            mn = Math.min(mn, Math.abs(k - or));
        }
        return mn;
    }
    protected int moveRight(int n, int[] bits, int or) {
        int t = n;
        while (t > 0) {
            int lb = t & -t;
            t -= lb;
            int i = 31 - Integer.numberOfLeadingZeros(lb);
            bits[i]++;
        }
        return or | n;
    }
    protected int moveLeft(int n, int[] bits, int or) {
        int t = n;
        while (t > 0) {
            int lb = t & -t;
            t -= lb;
            int i = 31 - Integer.numberOfLeadingZeros(lb);
            if (--bits[i] == 0) {
                or &= ~lb;
            }
        }
        return or;
    }
}
